package 力扣_排序算法.快排;

import java.util.Comparator;
import java.util.PriorityQueue;
import java.util.Random;

/**
 * @author zx
 * @create 2022-08-11 11:49
 */
public class 数组中的第K个最大元素_215 {
    public int findKthLargest3(int[] nums, int k) {
        for (int i = (nums.length - 1 - 1) / 2; i >= 0; i--) {
            siftDown(nums,i,nums.length);
        }
        for (int i = nums.length - 1; i > 0; i--) {
            swap(nums,0,i);
            siftDown(nums,0,i);
        }
        return nums[k - 1];
    }
    private void siftDown(int[] arr, int i, int length) {
        //还存在子树(条件a)
        while (2 * i + 1 < length) {
            int j = (i * 2) + 1;
            //判断一下是否有右子树
            if (j + 1 < length && arr[j + 1] < arr[j]) {
                //此时右树存在且大于左树的值
                j = j + 1;
            }
            // j就是左右子树的最大值
            if (arr[i] < arr[j]) {//条件(b)
                // 下沉结束
                break;
            }else {
                //循环结束后，就已经将树的最大值，放在了最顶
                swap(arr,i,j);
                i = j;
            }
        }
    }
    /**
     * @return 快速排序,但是时间复杂度不符合题目要求
     */
    public int findKthLargest(int[] nums, int k) {
        // 第 1 大的数,下标是 nums.length - 1;
        // 第 2 大的数,下标是 nums.length - 2;
        // ...
        // 第 k 大的数,下标是 nums.length - k;
        Random rnd = new Random();
        int target = nums.length - k;
        partition(nums,0, nums.length - 1,rnd);
        return nums[target];
    }
    private void partition(int[] arr, int l, int r, Random rnd) {
        if(l >= r){
            return;
        }
        int p = l + rnd.nextInt(r - l + 1);
        swap(arr, l, p);
        int v = arr[l];
        int lt = l;
        int i = lt + 1;
        int gt = r + 1;
        while(i < gt){
            if(arr[i] < v){
                swap(arr,i,lt + 1);
                i++;
                lt++;
            }else if(arr[i] > v){
                swap(arr,i,gt - 1);
                gt--;
            }else{
                i++;
            }
        }
        swap(arr,l,lt);
        partition(arr,l,lt - 1,rnd);
        partition(arr,gt,r,rnd);
    }
    private void swap(int[] arr, int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }

    /**
     * @return 最小堆
     */
    public int findKthLargest2(int[] nums, int k) {
        //最小堆
        PriorityQueue<Integer> queue = new PriorityQueue<>(new Comparator<Integer>(){
            @Override
            public int compare(Integer o1,Integer o2){
                return o1 - o2;
            }
        });

        for(int i = 0;i < nums.length;i++){
            if(queue.size() < k){
                queue.offer(nums[i]);
            }else{
                int peek = queue.peek();
                if(nums[i] < peek){
                    continue;
                }else{
                    queue.poll();
                    queue.offer(nums[i]);
                }
            }
        }
        return queue.poll();
    }
}
